package com.example.Arithmetic.Arithmetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 日期：2023/12/28
 * 时间：10:52
 * 描述：基数排序
 * 创建桶，依次从每一位上取出比较
 */
public class RadixSorting {
    public void sort(String[] a, int lenght) {
//        创建桶
        ArrayList<String>[] arrays = new ArrayList[128];
        for (int i = 0; i < arrays.length; i++) {
            arrays[i] = new ArrayList<>();
        }
//        遍历每一位，取出元素
        for (int i = lenght - 1; i >= 0; i--) {
//            放入每一个元素
            for (String s : a) {
                arrays[s.charAt(i)].add(s);
            }
//            取出所有元素
            int k = 0;
            for (List<String> list : arrays) {
                for (String s : list) {
                    a[k++] = s;
                }
                list.clear();
            }
            System.out.println(Arrays.toString(a));
        }
    }

    public static void main(String[] args) {
        String[] phoneNumbers = new String[10];
        phoneNumbers[0] = "1381234567b";
        phoneNumbers[1] = "1391234567r";
        phoneNumbers[2] = "1391234567a";
        phoneNumbers[3] = "13712345678";
        phoneNumbers[4] = "13512345678";
        phoneNumbers[5] = "13412345678";
        phoneNumbers[6] = "15012345678";
        phoneNumbers[7] = "15112345678";
        phoneNumbers[8] = "15212345678";
        phoneNumbers[9] = "15712345678";
        RadixSorting radixSorting = new RadixSorting();
        radixSorting.sort(phoneNumbers, 11);
        for (String phoneNumber : phoneNumbers) {
            System.out.println(phoneNumber);
        }
    }
}
